{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Score From Removing Stones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移除石子的最大得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在玩一个单人游戏，面前放置着大小分别为 <code>a</code>​​​​​​、<code>b</code> 和 <code>c</code>​​​​​​ 的 <strong>三堆</strong> 石子。</p>\n",
    "\n",
    "<p>每回合你都要从两个 <strong>不同的非空堆</strong> 中取出一颗石子，并在得分上加 <code>1</code> 分。当存在 <strong>两个或更多</strong> 的空堆时，游戏停止。</p>\n",
    "\n",
    "<p>给你三个整数 <code>a</code> 、<code>b</code> 和 <code>c</code> ，返回可以得到的 <strong>最大分数</strong> 。</p>\n",
    " \n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 2, b = 4, c = 6\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>石子起始状态是 (2, 4, 6) ，最优的一组操作是：\n",
    "- 从第一和第三堆取，石子状态现在是 (1, 4, 5)\n",
    "- 从第一和第三堆取，石子状态现在是 (0, 4, 4)\n",
    "- 从第二和第三堆取，石子状态现在是 (0, 3, 3)\n",
    "- 从第二和第三堆取，石子状态现在是 (0, 2, 2)\n",
    "- 从第二和第三堆取，石子状态现在是 (0, 1, 1)\n",
    "- 从第二和第三堆取，石子状态现在是 (0, 0, 0)\n",
    "总分：6 分 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 4, b = 4, c = 6\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>石子起始状态是 (4, 4, 6) ，最优的一组操作是：\n",
    "- 从第一和第二堆取，石子状态现在是 (3, 3, 6)\n",
    "- 从第一和第三堆取，石子状态现在是 (2, 3, 5)\n",
    "- 从第一和第三堆取，石子状态现在是 (1, 3, 4)\n",
    "- 从第一和第三堆取，石子状态现在是 (0, 3, 3)\n",
    "- 从第二和第三堆取，石子状态现在是 (0, 2, 2)\n",
    "- 从第二和第三堆取，石子状态现在是 (0, 1, 1)\n",
    "- 从第二和第三堆取，石子状态现在是 (0, 0, 0)\n",
    "总分：7 分 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 1, b = 8, c = 8\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>最优的一组操作是连续从第二和第三堆取 8 回合，直到将它们取空。\n",
    "注意，由于第二和第三堆已经空了，游戏结束，不能继续从第一堆中取石子。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= a, b, c <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-score-from-removing-stones](https://leetcode.cn/problems/maximum-score-from-removing-stones/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-score-from-removing-stones](https://leetcode.cn/problems/maximum-score-from-removing-stones/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n4\\n6', '4\\n4\\n6', '1\\n8\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            \n",
    "        \n",
    "        @cache\n",
    "        def dfs(node, par, one_left):\n",
    "\n",
    "            neis = [x for x in g[node] if x != par]\n",
    "            if not neis:\n",
    "                return values[node] if one_left else 0\n",
    "\n",
    "            return max(values[node] + sum(dfs(nei, node, one_left) for nei in neis), sum(dfs(nei, node, True) for nei in neis))\n",
    "\n",
    "\n",
    "        return dfs(0, -1, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for i in range(n)]\n",
    "        deg = [0] * n\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "            deg[i] += 1\n",
    "            deg[j] += 1\n",
    "        deg[0] += 1\n",
    "\n",
    "        ans = [float('inf')] * n\n",
    "        queue = deque()\n",
    "        for idx, i in enumerate(deg):\n",
    "            if i == 1:\n",
    "                queue.append(idx)\n",
    "                ans[idx] = values[idx]\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for i in g[node]:\n",
    "                deg[i] -= 1\n",
    "                if deg[i] == 1:\n",
    "                    children = sum([ans[x] for x in g[i] if deg[x] <= 1])\n",
    "                    ans[i] = min(values[i], children)\n",
    "                    queue.append(i)\n",
    "\n",
    "        return sum(values) - ans[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "\n",
    "        dp1 = [0 for _ in range(n)]\n",
    "        dp2 = [0 for _ in range(n)]\n",
    "        stack = [(0, -1)]\n",
    "        while stack:\n",
    "            # bujiankang, jiankang\n",
    "            x, fa = stack.pop()\n",
    "            if x >= 0:\n",
    "                stack.append((~x, fa))\n",
    "                for y in dct[x]:\n",
    "                    if y != fa:\n",
    "                        stack.append((y, x))\n",
    "            else:\n",
    "                x = ~x\n",
    "                res1 = res2 = 0\n",
    "                res1 += values[x]\n",
    "                a21 = 0\n",
    "                a22 = values[x]\n",
    "                flag = 0\n",
    "                for y in dct[x]:\n",
    "                    if y != fa:\n",
    "                        nex1, nex2 = dp1[y], dp2[y]\n",
    "                        res1 += nex1\n",
    "                        a21 += nex1 if nex1 > nex2 else nex2\n",
    "                        flag = 1\n",
    "                        a22 += nex2\n",
    "                if not flag:\n",
    "                    a22 = -inf\n",
    "                dp1[x] = res1\n",
    "                dp2[x] = a22 if a22 > a21 else a21\n",
    "\n",
    "        return dp2[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for i in range(n)]\n",
    "        for (u,v) in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        topo = []\n",
    "        G, Q = [[] for i in range(n)], deque([0]) \n",
    "        while Q:\n",
    "            u= Q.popleft()\n",
    "            topo.append(u)\n",
    "            for v in g[u]:\n",
    "                if G[v]: continue\n",
    "                G[u].append(v)\n",
    "                Q.append(v)\n",
    "        topo.reverse()\n",
    "\n",
    "        sums = [0]*n\n",
    "        f = [0]*n\n",
    "        for u in topo:\n",
    "            if not G[u]: continue\n",
    "            for v in G[u]:\n",
    "                sums[u] += (sums[v] + values[v])\n",
    "                f[u] += f[v]\n",
    "            f[u] = max(f[u]+values[u], sums[u])\n",
    "\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        adj = {}\n",
    "        for u, v in edges:\n",
    "            adj[v] = adj.get(v, []) + [u]\n",
    "            adj[u] = adj.get(u, []) + [v]\n",
    "        children = {}\n",
    "        unvisited = [True] * n\n",
    "        dq = deque([0])\n",
    "        seq = []\n",
    "        while dq:\n",
    "            u = dq.popleft()\n",
    "            if unvisited[u]:\n",
    "                seq.append(u)\n",
    "                unvisited[u] = False\n",
    "                for v in adj[u]:\n",
    "                    if unvisited[v]:\n",
    "                        children[u] = children.get(u, []) + [v]\n",
    "                        dq.append(v)\n",
    "        cs = [0] * n\n",
    "        for u in seq[::-1]:\n",
    "            for v in children.get(u, []):\n",
    "                cs[u] += cs[v] + values[v]\n",
    "        dp = [0] * n\n",
    "        for u in seq[::-1]:\n",
    "            if children.get(u, []):\n",
    "                total = values[u]\n",
    "                for v in children.get(u, []):\n",
    "                    total += dp[v]\n",
    "                dp[u] = max(cs[u], total)\n",
    "        return dp[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for _ in range(n)]\n",
    "        parent = [-1] * n\n",
    "        for e in edges:\n",
    "            g[e[0]].append(e[1])\n",
    "            g[e[1]].append(e[0])\n",
    "        q, head = [0], -1\n",
    "        visited = [False] * n\n",
    "        visited[0] = True\n",
    "        kids = [[] for _ in range(n)]\n",
    "        while head + 1 < len(q):\n",
    "            head += 1\n",
    "            u = q[head]\n",
    "            for v in g[u]:\n",
    "                if visited[v]:\n",
    "                    continue\n",
    "                q.append(v)\n",
    "                visited[v] = True\n",
    "                parent[v] = u\n",
    "                kids[u].append(v)\n",
    "        f = [[0, 0] for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            u = q[i]\n",
    "            p = parent[u]\n",
    "            if len(kids[u]) > 0:\n",
    "                f[u][1] += values[u]\n",
    "            if p != -1:\n",
    "                f[p][0] += values[u] + f[u][0]\n",
    "                f[p][1] += max(f[u])\n",
    "        return max(f[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "\n",
    "        n = len(values)\n",
    "        lk = [[] for i in range(n)]\n",
    "        ch = [[] for i in range(n)]\n",
    "\n",
    "        for a, b in edges:\n",
    "            lk[a].append(b)\n",
    "            lk[b].append(a)\n",
    "\n",
    "        vis = [0] * n\n",
    "\n",
    "        que = deque()\n",
    "        que.append(0)\n",
    "        vis[0] = 1\n",
    "        tt = []\n",
    "        while len(que):\n",
    "            x = que.popleft()\n",
    "            tt.append(x)\n",
    "\n",
    "            for y in lk[x]:\n",
    "                if vis[y] == 0:\n",
    "                    vis[y] = 1\n",
    "                    que.append(y)\n",
    "                    ch[x].append(y)\n",
    "\n",
    "\n",
    "        dp = [[0, 0] for i in range(n)]\n",
    "\n",
    "        for x in tt[::-1]:\n",
    "            if len(ch[x]) == 0:\n",
    "                dp[x][1] = values[x]\n",
    "                dp[x][0] = 0\n",
    "\n",
    "                continue\n",
    "\n",
    "            dp[x][1] = values[x]\n",
    "            for y in ch[x]:\n",
    "                dp[x][1] += dp[y][1]\n",
    "\n",
    "\n",
    "            val1 = 0\n",
    "            for y in ch[x]:\n",
    "                val1 += dp[y][1]\n",
    "\n",
    "            val2 = values[x]\n",
    "            for y in ch[x]:\n",
    "                val2 += dp[y][0]\n",
    "\n",
    "            dp[x][0] = max(val1, val2)\n",
    "\n",
    "        return dp[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        afterDict = defaultdict(list)\n",
    "        layerDict = defaultdict(int)\n",
    "        reverseLayerDict = defaultdict(list)\n",
    "        maxLayer = 0\n",
    "        \n",
    "        edgeDict = defaultdict(set)\n",
    "        for edge in edges:\n",
    "            edgeDict[edge[0]].add(edge[1])\n",
    "            edgeDict[edge[1]].add(edge[0])\n",
    "        \n",
    "        toBeCount = [0]\n",
    "        layerDict[0] = 1\n",
    "        while len(toBeCount) != 0:\n",
    "            tmp = toBeCount[0]\n",
    "            for i in edgeDict[tmp]:\n",
    "                if layerDict[i] == 0:\n",
    "                    toBeCount.append(i)\n",
    "                    afterDict[tmp].append(i)\n",
    "                    layerDict[i] = layerDict[tmp] + 1\n",
    "                    maxLayer = layerDict[i]\n",
    "            toBeCount.pop(0)\n",
    "            \n",
    "        for key in layerDict.keys():\n",
    "            reverseLayerDict[layerDict[key]].append(key)\n",
    "            \n",
    "        dp = [[0, 0] for i in range(len(values))]\n",
    "        \n",
    "        for layer in range(maxLayer, 0, -1):\n",
    "            nodes = reverseLayerDict[layer]\n",
    "            if layer == maxLayer:\n",
    "                for node in nodes:\n",
    "                    dp[node][0] = 0\n",
    "                    dp[node][1] = -1\n",
    "            else:\n",
    "                for node in nodes:\n",
    "                    # dp[node][0] 若这个节点不去掉，后面的节点随便你去不去掉\n",
    "                    afterNodes = afterDict[node]\n",
    "                    if len(afterNodes) == 0:\n",
    "                        dp[node][0] = 0\n",
    "                        dp[node][1] = -1\n",
    "                    else:\n",
    "                        dp[node][1] += values[node]\n",
    "                        for afterNode in afterNodes:\n",
    "                            dp[node][0] += max(values[afterNode] + dp[afterNode][0], dp[afterNode][1])\n",
    "                            dp[node][1] += max(dp[afterNode][0], dp[afterNode][1])\n",
    "            \n",
    "        \n",
    "        return max(dp[node][0], dp[node][1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        self.e = [[] for _ in range(n)]\n",
    "        self.s = [0] * n\n",
    "        self.s2 = [0] * n\n",
    "        self.values = values\n",
    "        for edge in edges:\n",
    "            self.e[edge[0]].append(edge[1])\n",
    "            self.e[edge[1]].append(edge[0])\n",
    "        self.dfs(0, -1)\n",
    "        return self.s2[0]\n",
    "    \n",
    "    def dfs(self, v, f):\n",
    "        # print(v, f)\n",
    "        son_s2 = 0\n",
    "        is_leaf = True\n",
    "        for u in self.e[v]:\n",
    "            if u != f:\n",
    "                is_leaf = False\n",
    "                self.dfs(u, v)\n",
    "                self.s[v] += self.s[u] + self.values[u]\n",
    "                son_s2 += self.s2[u]\n",
    "        if not is_leaf:\n",
    "            self.s2[v] = max(self.values[v] + son_s2, self.s[v])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int: \n",
    "        s=sum(values)\n",
    "        n = len(values)\n",
    "        outs = [[] for _ in range(0,n)]\n",
    "        for v in edges:\n",
    "            outs[v[0]].append(v[1])\n",
    "            outs[v[1]].append(v[0])\n",
    "        m = dict()\n",
    "        return s-self.dfs(0,outs,values,m) \n",
    "    def dfs(self, root, outs, values, m):\n",
    "        m[root]=1\n",
    "        if len(outs[root])==0:\n",
    "            return values[root]\n",
    "        sum=0\n",
    "        for v in outs[root]:\n",
    "            if m.get(v) is None:\n",
    "                sum+=self.dfs(v,outs,values,m)\n",
    "        if sum==0:\n",
    "            return values[root]\n",
    "        return min(sum,values[root])        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n=len(values);edge,f=[[] for i in range(n)],[[0,0] for i in range(n)]\n",
    "        for i in edges:edge[i[0]].append(i[1]);edge[i[1]].append(i[0])\n",
    "        def dfs(u,v):\n",
    "            for i in edge[u]:\n",
    "                if(i!=v):\n",
    "                    dfs(i,u)\n",
    "                    f[u][0]+=f[i][0]\n",
    "                    f[u][1]+=f[i][1]\n",
    "            if(f[u][0]!=0):f[u][1]=max(f[u][1]+values[u],f[u][0])\n",
    "            f[u][0]+=values[u]\n",
    "        dfs(0,0)\n",
    "        return f[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g=[[] for _ in values]\n",
    "        g[0].append(-1)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x:int,fa:int)->int:\n",
    "            if len(g[x])==1:\n",
    "                return values[x]\n",
    "            loss=0\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    loss+=dfs(y,x)\n",
    "            return min(loss,values[x])\n",
    "        return sum(values)-dfs(0,-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, e: List[List[int]], v: List[int]) -> int:\n",
    "        n=len(e)+1\n",
    "        tree=[[] for i in range(n)]\n",
    "        for i,j in e:\n",
    "            tree[i].append(j)\n",
    "            tree[j].append(i)\n",
    "        def dfs(u,fa):\n",
    "            sf=st=0\n",
    "            for i in tree[u]:\n",
    "                if fa!=i:\n",
    "                    t,f=dfs(i,u)\n",
    "                    sf+=f\n",
    "                    st+=t\n",
    "            t=max(sf,st+v[u]) if sf>0 else 0\n",
    "            f=sf+v[u]\n",
    "            return t,f\n",
    "        t,f=dfs(0,-1)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def dfs(u, fa):\n",
    "            if len(g[u]) == 1 and fa != -1:\n",
    "                return values[u], 0\n",
    "            f1, f2 = 0, 0\n",
    "            \n",
    "            for j in g[u]:\n",
    "                if j != fa:\n",
    "                    g1, g2 = dfs(j, u)\n",
    "                    f1 += g1\n",
    "                    f2 += g2\n",
    "            return f1 + values[u], max(f1, f2 + values[u])\n",
    "        return dfs(0, -1)[1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        menu = {}\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i][0] in menu:\n",
    "                menu[edges[i][0]].append(edges[i][1])\n",
    "            else:\n",
    "                menu[edges[i][0]]=[edges[i][1]]\n",
    "            if edges[i][1] in menu:\n",
    "                menu[edges[i][1]].append(edges[i][0])\n",
    "            else:\n",
    "                menu[edges[i][1]]=[edges[i][0]]\n",
    "        menu[0].append(-1)\n",
    "        def dps(root,fa):\n",
    "            if len(menu[root])==1:\n",
    "                return values[root]\n",
    "            tmp=0\n",
    "            for node in menu[root]:\n",
    "                if node == fa:\n",
    "                    continue\n",
    "                tmp+=dps(node,root)\n",
    "            \n",
    "            return min(values[root],tmp)\n",
    "        return sum(values)-dps(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        dic = {}\n",
    "        dicS = {}\n",
    "        dicC = {}\n",
    "        for i in range(len(edges)):\n",
    "            n1, n2 = edges[i][0], edges[i][1]\n",
    "            if(n1 in dic):\n",
    "                dic[n1].append(n2)\n",
    "            else:\n",
    "                dic[n1] = [n2]\n",
    "            if(n2 in dic):\n",
    "                dic[n2].append(n1)\n",
    "            else:\n",
    "                dic[n2] = [n1]\n",
    "\n",
    "        def cal(parent, father):\n",
    "            if(len(dic[parent]) == 1 and dic[parent][0] == father):\n",
    "                return 0\n",
    "            if(parent in dicC):\n",
    "                return dicC[parent]\n",
    "            s0 = 0\n",
    "            s1 = values[parent]\n",
    "            for item in dic[parent]:\n",
    "                if(item != father):\n",
    "                    s0 += sumP(item, parent)\n",
    "                    s1 += cal(item, parent)\n",
    "            dicC[parent] = max(s0,s1)\n",
    "            return max(s0, s1)\n",
    "\n",
    "\n",
    "        def sumP(parent, father):\n",
    "            if(len(dic[parent]) == 1 and dic[parent][0] == father):\n",
    "                return values[parent]\n",
    "            if(parent in dicS):\n",
    "                return dicS[parent]\n",
    "            ans = values[parent]\n",
    "            for item in dic[parent]:\n",
    "                if(item != father):\n",
    "                    ans += sumP(item, parent)\n",
    "            dicS[parent] = ans\n",
    "            return ans\n",
    "\n",
    "        return cal(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        dp = [[] for _ in range(len(values))]\n",
    "        for i in edges:\n",
    "            dp[i[0]].append(i[1])\n",
    "            dp[i[1]].append(i[0])\n",
    "        dp[0].append(-1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            dp1 = 0\n",
    "            dp2 = 0\n",
    "\n",
    "            if len(dp[i]) == 1:\n",
    "                return values[i], 0\n",
    "\n",
    "            for ii in dp[i]:\n",
    "                if j!=ii:\n",
    "                    a1,a2 = dfs(ii,i)\n",
    "                    dp1 += a1\n",
    "                    dp2 += a2\n",
    "\n",
    "            return dp1+values[i], max(dp2+values[i], dp1)\n",
    "        \n",
    "        return dfs(0,-1)[1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        gird = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            gird[i].append(j)\n",
    "            gird[j].append(i)\n",
    "        visited = [False]*n\n",
    "        b = [0] * n\n",
    "        def dfs0(i):\n",
    "            visited[i] = True\n",
    "            if b[i]: return b[i]\n",
    "            res = values[i]\n",
    "            \n",
    "            for j in gird[i]:\n",
    "                if j != i and not visited[j]:\n",
    "                    res += dfs0(j)\n",
    "            b[i] = res\n",
    "            return res\n",
    "        dfs0(0)\n",
    "        visited = [False]*n\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            visited[i] = True\n",
    "            if i != 0 and len(gird[i]) == 1:\n",
    "                return 0\n",
    "            # 不选\n",
    "            res1 = b[i] - values[i]\n",
    "            \n",
    "            #选\n",
    "            res2 = values[i]\n",
    "            for j in gird[i]:\n",
    "                if j != i and not visited[j]:\n",
    "                    res2 += dfs(j)\n",
    "            return max(res1, res2)\n",
    "        return dfs(0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        # 每个元素可以加入到分数  也可以不加入\n",
    "        # 当前元素如果不加入，那么所有的孩子都全都可以加入\n",
    "        # 如果当前元素加入，那么所有的孩子都必须要收礼物\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        \n",
    "        # s==0 还没选择过\n",
    "        # s==1 不需要保留了\n",
    "        @cache\n",
    "        def dfs(node, fa,s):\n",
    "            if len(graph[node]) == 1 and node != 0:\n",
    "                #叶子\n",
    "                if s == 0: return 0\n",
    "                return values[node]\n",
    "            \n",
    "            sel = 0\n",
    "            unsel = values[node]\n",
    "            for next in graph[node]:\n",
    "                if next != fa:\n",
    "                    sel += dfs(next,node,1)\n",
    "                    unsel += dfs(next,node,0)\n",
    "            if s == 0: return max(sel, unsel)\n",
    "            return sel + values[node]\n",
    "            \n",
    "        return dfs(0,-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        d = collections.defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            d[u].add(v)\n",
    "            d[v].add(u)\n",
    "        def dfs(last, u):\n",
    "            ans1 = 0\n",
    "            ans2 = 0\n",
    "            for v in d[u]:\n",
    "                if v != last:\n",
    "                    value1, value2 = dfs(u, v)\n",
    "                    ans1 += value1\n",
    "                    ans2 += value2\n",
    "            out1 = ans1 + values[u]\n",
    "            if ans1 == 0:\n",
    "                out2 = 0\n",
    "            else:\n",
    "                out2 = max(ans2 + values[u], ans1)\n",
    "            return out1, out2\n",
    "        return dfs(-1, 0)[1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = [[] for _ in values]\n",
    "        g[0].append(-1)  # 避免误把根节点当作叶子\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        @cache\n",
    "        def dfs(cnode:int, isfather, father):\n",
    "            if isfather:\n",
    "                return values[cnode] + sum(dfs(son, True, cnode) for son in g[cnode] if son != father)\n",
    "            else:\n",
    "                sons = g[cnode]\n",
    "                if len(sons) == 1:\n",
    "                    if values[cnode]:\n",
    "                        return 0\n",
    "                    else:\n",
    "                        return -1\n",
    "                if values[cnode]:\n",
    "                    res_val = values[cnode]\n",
    "                    for son in sons:\n",
    "                        if son == father:\n",
    "                            continue\n",
    "                        a = dfs(son, False, cnode)\n",
    "                        if a == -1:\n",
    "                            res_val = -1\n",
    "                            break\n",
    "                        res_val += a\n",
    "                    return max(sum(dfs(son, True, cnode) for son in g[cnode] if son != father), res_val)\n",
    "                else:\n",
    "                    res_val = 0\n",
    "                    for son in sons:\n",
    "                        a = dfs(son, False, cnode)\n",
    "                        if a == -1:\n",
    "                            res_val = -1\n",
    "                            break\n",
    "                        res_val += a\n",
    "                    return res_val\n",
    "        # return dfs(0, False)\n",
    "\n",
    "            \n",
    "        return dfs(0, False, -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        d = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            d[a].append(b)\n",
    "            d[b].append(a)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur, far, save):\n",
    "            if cur != 0 and len(d[cur]) == 1 and not save:\n",
    "                return 0\n",
    "            res1, res2 = 0, values[cur] #不选， 选\n",
    "            for nxt in d[cur]:\n",
    "                if nxt != far:\n",
    "                    res1 += dfs(nxt, cur, True)\n",
    "                    res2 += dfs(nxt, cur, save)\n",
    "            return max(res1, res2)\n",
    "        \n",
    "        return dfs(0, -1, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "            \n",
    "        @lru_cache(None)\n",
    "        def dfs(u, p, have_point):\n",
    "            if have_point:\n",
    "                ans = values[u]\n",
    "                for v in graph[u]:\n",
    "                    if v == p:\n",
    "                        continue\n",
    "                    ans += dfs(v, u, True)\n",
    "                return ans\n",
    "            else:\n",
    "                if len(graph[u]) == 1 and p != -1:\n",
    "                    return 0\n",
    "                ans1, ans2 = 0, values[u]\n",
    "                for v in graph[u]:\n",
    "                    if v == p:\n",
    "                        continue\n",
    "                    ans1 += dfs(v, u, True)\n",
    "                    ans2 += dfs(v, u, False)\n",
    "                return max(ans1, ans2)\n",
    "        \n",
    "        return dfs(0, -1, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        # s->0 上面还没选过，  s->1 上面已经选过了\n",
    "        @cache\n",
    "        def dfs(node, fa, s):\n",
    "            if s == 1:\n",
    "                ans = values[node]\n",
    "                for next in graph[node]:\n",
    "                    if next != fa:\n",
    "                        ans += dfs(next, node, 1)\n",
    "                return ans\n",
    "            if len(graph[node]) == 1 and node != 0:\n",
    "                return 0\n",
    "            #可以选择保留这个节点\n",
    "            ans = 0\n",
    "            for next in graph[node]:\n",
    "                if next != fa:\n",
    "                    ans += dfs(next, node,1)\n",
    "\n",
    "            #也可以选择不保留\n",
    "            notsel = values[node]\n",
    "            for next in graph[node]:\n",
    "                if next != fa:\n",
    "                    notsel += dfs(next, node, 0)\n",
    "            return max(ans, notsel)\n",
    "        return dfs(0,-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        n = len(edges) + 1\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(u, fa, st, valid):\n",
    "            if len(g[u]) == 1 and g[u][0] == fa and not valid: return 0\n",
    "            cur = values[u] if st else 0\n",
    "            res1 = res2 = res3 = 0\n",
    "            if valid:\n",
    "                for nxt in g[u]:\n",
    "                    if nxt == fa: continue\n",
    "                    res1 += dfs(nxt, u, 1, 1)\n",
    "            else:\n",
    "                if st == 1:\n",
    "                    for nxt in g[u]:\n",
    "                        if nxt == fa: continue\n",
    "                        res2 += max(dfs(nxt, u, 1, 0), dfs(nxt, u, 0, 1))\n",
    "                else:\n",
    "                    for nxt in g[u]:\n",
    "                        if nxt == fa: continue\n",
    "                        res3 += dfs(nxt, u, 1, 1)\n",
    "            return max(res1, res2, res3) + cur\n",
    "        return max(dfs(0, -1, 0, 1), dfs(0, -1, 1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maximumScoreAfterOperations(self, edges, values):\n",
    "\n",
    "        n = len(values)\n",
    "        childrens = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            childrens[a] += [b]\n",
    "            childrens[b] += [a]\n",
    "\n",
    "        visited = [False for _ in range(n)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(node, reserve):\n",
    "            children = []\n",
    "            for child in childrens[node]:\n",
    "                if not visited[child]:\n",
    "                    children += [child]\n",
    "\n",
    "            value = values[node]\n",
    "            if not children:\n",
    "                return 0 if not reserve else value\n",
    "\n",
    "            scores = []\n",
    "            if not reserve:\n",
    "                score = 0\n",
    "                for child in children:\n",
    "                    visited[child] = True\n",
    "                    score += dfs(child, True)\n",
    "                    visited[child] = False\n",
    "                scores += [score]\n",
    "\n",
    "            score = 0\n",
    "            for child in children:\n",
    "                visited[child] = True\n",
    "                score += dfs(child, reserve)\n",
    "                visited[child] = False\n",
    "            scores += [score + value]\n",
    "\n",
    "            return max(scores)\n",
    "\n",
    "        visited[0] = True\n",
    "        return dfs(0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n=len(values)\n",
    "        children=[set() for _ in range(n)]\n",
    "        visited=set([0])\n",
    "        def add(i):\n",
    "            visited.add(i)\n",
    "            for j in children[i]:\n",
    "                children[j].remove(i)\n",
    "                add(j)\n",
    "                \n",
    "        for i,j in edges:\n",
    "            if i in visited:\n",
    "                children[i].add(j)\n",
    "                add(j)\n",
    "            elif j in visited:\n",
    "                children[j].add(i)\n",
    "                add(i)\n",
    "            else:\n",
    "                children[i].add(j)\n",
    "                children[j].add(i)\n",
    "                \n",
    "        @cache\n",
    "        def f(i,keep):\n",
    "            ans=0\n",
    "            for c in children[i]:\n",
    "                ans+=f(c,False)\n",
    "            if not keep:\n",
    "                return ans+values[i]\n",
    "            ans1=0\n",
    "            if not children[i]:\n",
    "                return 0\n",
    "            for c in children[i]:\n",
    "                ans1+=f(c,True)\n",
    "            # print(i,'qu:',ans1+values[i],'buqu:',ans)\n",
    "            return max(ans,ans1+values[i])\n",
    "    \n",
    "        return f(0,True)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        # dp(i, flag): 表示以i为根节点的树能达到的最大和，flag表示是否上面已有非0\n",
    "        \n",
    "        node2child = collections.defaultdict(set)\n",
    "        for edge in edges:\n",
    "            node2child[edge[0]].add(edge[1])\n",
    "            node2child[edge[1]].add(edge[0])\n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            idx = stack[0]\n",
    "            stack = stack[1:]\n",
    "            for child in node2child[idx]:\n",
    "                node2child[child].remove(idx)\n",
    "                stack.append(child)\n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "        @cache\n",
    "        def dp(i, flag):\n",
    "            if not node2child[i]:\n",
    "                if flag:\n",
    "                    if values[i] == 0:\n",
    "                        return -float(\"inf\")\n",
    "                    else:\n",
    "                        return 0\n",
    "                else:\n",
    "                    ans = values[i]\n",
    "                    return ans\n",
    "            else:\n",
    "                if not flag:\n",
    "                    ans = values[i]\n",
    "                    for child in list(node2child[i]):\n",
    "                        ans += dp(child, False)\n",
    "                    return ans\n",
    "                else:\n",
    "                    if values[i] == 0:\n",
    "                        ans = 0\n",
    "                        for child in list(node2child[i]):\n",
    "                            ans = ans + dp(child, True)\n",
    "                        return ans\n",
    "                    else:\n",
    "                        ans1 = 0\n",
    "                        # case 1:\n",
    "                        for child in list(node2child[i]):\n",
    "                            ans1 = ans1 + dp(child, False)\n",
    "                        # case 2:\n",
    "                        ans2 = values[i]\n",
    "                        for child in list(node2child[i]):\n",
    "                            ans2 = ans2 + dp(child, True)\n",
    "                        if ans2 > ans1:\n",
    "                            return ans2\n",
    "                        else:\n",
    "                            return ans1\n",
    "        return dp(0, True)\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], val: List[int]) -> int:\n",
    "        n=len(edges)+1\n",
    "        g=[[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        vis=[False]*n\n",
    "        t=[[] for _ in range(n)]\n",
    "        def tree(node):\n",
    "            vis[node]=True\n",
    "            son=[x for x in g[node] if not vis[x]]\n",
    "            t[node].extend(son)\n",
    "            for next in son:\n",
    "                tree(next)\n",
    "        tree(0)\n",
    "        # print(t)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(node:int,select:bool)->tuple[int]:\n",
    "            if not t[node]:\n",
    "                if select:\n",
    "                    return (0,val[node])\n",
    "                else:\n",
    "                    return (0,0)\n",
    "            if select:\n",
    "                ans=0\n",
    "                for son in t[node]:\n",
    "                    ans+=dfs(son,True)[1]\n",
    "                return (ans,ans+val[node])\n",
    "            else:\n",
    "                a=0\n",
    "                b=val[node]\n",
    "                for son in t[node]:\n",
    "                    x,y=dfs(son,select)\n",
    "                    i,j=dfs(son,True)\n",
    "                    a+=max(i,j)\n",
    "                    b+=max(x,y)\n",
    "                return (a,b)\n",
    "        return max(dfs(0,False))\n",
    "    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for f,t in edges:\n",
    "            children[f].append(t)\n",
    "            children[t].append(f)\n",
    "        \n",
    "        def dfs(i, fa):\n",
    "            ss = sum(dfs(c, i) for c in children[i] if c!=fa)\n",
    "            if ss>0: return min(values[i],ss)\n",
    "            return values[i]\n",
    "        return sum(values) - dfs(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        path = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            path[x].append(y)\n",
    "            path[y].append(x)\n",
    "        def dfs(cur, prev):\n",
    "            if cur != 0 and len(path[cur]) == 1:\n",
    "                return values[cur]\n",
    "            return min(values[cur], sum(dfs(next, cur) for next in path[cur] if next != prev))\n",
    "        return sum(values) - dfs(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = [[] for _ in values]\n",
    "        g[0].append(-1)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        total = [0] * len(values)\n",
    "        def cal_sum(u, fa):\n",
    "            total[u] = values[u]\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    cal_sum(v, u)\n",
    "                    total[u] += total[v]\n",
    "\n",
    "        cal_sum(0, -1)\n",
    "\n",
    "        def dfs(u, fa):\n",
    "            if len(g[u]) == 1:\n",
    "                return 0 \n",
    "            not_do = sum(total[v] for v in g[u] if v != fa)\n",
    "            do_it = values[u] + sum(dfs(v, u) for v in g[u] if v != fa)\n",
    "            return max(not_do, do_it)\n",
    "\n",
    "        return dfs(0, -1)\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # g = [[] for _ in values]\n",
    "        # g[0].append(-1)  # 避免误把根节点当作叶子\n",
    "        # for x, y in edges:\n",
    "        #     g[x].append(y)\n",
    "        #     g[y].append(x)\n",
    "\n",
    "        # # dfs(x, fa) 计算以 x 为根的子树是健康时，失去的最小分数\n",
    "        # def dfs(x: int, fa: int) -> int:\n",
    "        #     if len(g[x]) == 1:  # x 是叶子\n",
    "        #         return values[x]\n",
    "        #     loss = 0  # 第二种情况\n",
    "        #     for y in g[x]:\n",
    "        #         if y != fa:\n",
    "        #             loss += dfs(y, x)  # 计算以 y 为根的子树是健康时，失去的最小分数\n",
    "        #     return min(values[x], loss)  # 两种情况取最小值\n",
    "        # return sum(values) - dfs(0, -1)\n",
    "\n",
    "\n",
    "        # n = len(values)\n",
    "        # graph = [[] for _ in range(n)]\n",
    "        # outDegree = [0]*n\n",
    "\n",
    "        # for u, v in edges:\n",
    "        #     graph[u].append(v)\n",
    "        #     outDegree[u] += 1\n",
    "\n",
    "        # def isHealthy(root):\n",
    "        #     if values[root] == 0 and not graph[root]:\n",
    "        #         return False\n",
    "        #     for nxt in graph[root]:\n",
    "        #         values[nxt] = values[root] + values[nxt]\n",
    "        #         if values[nxt] == 0 and not isHealthy(nxt):\n",
    "        #             return False        \n",
    "        #     return True\n",
    "\n",
    "        # dp = [0] * n \n",
    "        # base case\n",
    "        # for i in range(n):\n",
    "        #     if not graph[i]:  # 叶子结点\n",
    "        #         dp[i] = values[i]\n",
    "        \n",
    "        # dp[i] = max(values[i] + dp[graph[i]], values[graph[i]])  # max(选自己， 不选自己)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        # 构造一颗树\n",
    "        g = [[] for _ in values]\n",
    "        g[0].append(-1)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        # total[i]表示以节点i为根节点的子树的元素和\n",
    "        total = [0] * len(values)\n",
    "\n",
    "        def cal_sum(u, fa):\n",
    "            # 第一次dfs，计算整棵树的元素和\n",
    "            total[u] = values[u]\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    cal_sum(v, u)\n",
    "                    total[u] += total[v]\n",
    "        cal_sum(0, -1)\n",
    "\n",
    "        def dfs(u, fa):\n",
    "            if len(g[u]) == 1:\n",
    "                return 0\n",
    "            # 不选当前节点，可以选所有u的子树之和（不含u）\n",
    "            f0 = sum(total[v] for v in g[u] if v!= fa)\n",
    "\n",
    "            # 选当前节点，转化为求以v为根的子树是健康的能获得的最大分数\n",
    "            f1 = values[u] + sum(dfs(v, u) for v in g[u] if v != fa)\n",
    "\n",
    "            return max(f0, f1)\n",
    "        return dfs(0, -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = [[] for _ in values]\n",
    "        g[0].append(-1)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        @cache\n",
    "        def cal_sum(u, fa):\n",
    "            tot = values[u]\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    tot += cal_sum(v, u)\n",
    "            return tot\n",
    "        \n",
    "        # 以u为根的子树是健康的能获得的最大分数\n",
    "        def dfs(u, fa):\n",
    "            if len(g[u]) == 1:\n",
    "                return 0\n",
    "            #不选当前节点，可以选所有u的子树之和（不含u）\n",
    "            f0 = sum(cal_sum(v, u) for v in g[u] if v != fa)\n",
    "            \n",
    "            #选当前节点，转化为求以v为根的子树是健康的能获得的最大分数\n",
    "            f1 = values[u] + sum(dfs(v, u) for v in g[u] if v != fa)\n",
    "            return max(f0, f1)\n",
    "        \n",
    "        return dfs(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        dp = [[0] * (m + 1) for _ in range(m+1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for left in range(i + 1):\n",
    "                right = n - 1 - (i - left)\n",
    "                dp[i][left] = max(multipliers[i] * nums[left] + dp[i + 1][left + 1],\n",
    "                                  multipliers[i] * nums[right] + dp[i + 1][left])\n",
    "\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "\n",
    "        # hard题目 -- 动态规划解法出现的频率相对高点\n",
    "        # 最后的结果 -- 开头取i(0-m)个,末尾取j=m-i个 dp[i][j]\n",
    "        n,m = len(nums),len(multipliers)\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            dp[0][i] = dp[0][i-1]+nums[n-i]*multipliers[i-1]\n",
    "            dp[i][0] = dp[i-1][0]+nums[i-1]*multipliers[i-1]\n",
    "        res = max(dp[0][m],dp[m][0])\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for k in range(i+1,m+1):\n",
    "                dp[i][k-i] = max(dp[i-1][k-i]+nums[i-1]*multipliers[k-1],dp[i][k-i-1]+nums[n-(k-i)]*multipliers[k-1])\n",
    "                if k == m:res = max(res,dp[i][k-i])\n",
    "        return res\n",
    "\n",
    "        # 深度优先搜索 -- 终止条件\n",
    "        # 由于mn规模过大,dfs超时 -- 本题使用动态规划！\n",
    "        # n,m = len(nums),len(multipliers)\n",
    "        # res = []\n",
    "        # def dfs(arr,count,total):\n",
    "        #     if count == m:\n",
    "        #         res.append(total)\n",
    "        #         return \n",
    "        #     if arr[0] == arr[-1]:\n",
    "        #         dfs([],count+1,total+arr[0]*multipliers[-1])\n",
    "        #     else:\n",
    "        #         tmp = [[0,len(arr)-1,-1],[1,len(arr),0]]\n",
    "        #         for i,j,k in tmp:\n",
    "        #             dfs(arr[i:j],count+1,total+arr[k]*multipliers[count])\n",
    "        #     return    \n",
    "        # dfs(nums,0,0)\n",
    "        # return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        m = len(multipliers)\n",
    "        n = len(nums)\n",
    "        dp = [[-10**9 for i in range(m+1)] for j in range(m+1)]\n",
    "        dp[1][1] = nums[0]*multipliers[0]\n",
    "        dp[1][0] = nums[-1]*multipliers[0]\n",
    "        for i in range(2,m+1):\n",
    "            for j in range(i+1):\n",
    "                dp[i][j] = max(dp[i][j],dp[i-1][j-1]+multipliers[i-1]*nums[j-1])\n",
    "                if j < i:\n",
    "                    dp[i][j] = max(dp[i][j],dp[i-1][j]+multipliers[i-1]*nums[n-i+j])\n",
    "        res = -10**9\n",
    "        for i in range(m+1):\n",
    "            res = max(res,dp[m][i])\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], muls: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(muls)\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "        ans = float('-inf')\n",
    "        for k in range(1, m+1):\n",
    "            for i in range(0, k+1):\n",
    "                if i == 0:\n",
    "                    dp[i][k-i] = dp[i][k-i-1] + nums[n-k+i]*muls[k-1]\n",
    "                elif i == k:\n",
    "                    dp[i][k-i] = dp[i-1][k-i] + nums[i-1]*muls[k-1]\n",
    "                else:\n",
    "                    dp[i][k-i] = max(dp[i][k-i-1] + nums[n-k+i]*muls[k-1], dp[i-1][k-i] + nums[i-1]*muls[k-1])\n",
    "                if (k == m):\n",
    "                    ans = max(ans, dp[i][k-i])\n",
    "            \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], muls: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(muls)\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(m-i-1, -1, -1):\n",
    "                dp[i][j] = max(dp[i+1][j] + muls[i + j]*nums[i], dp[i][j+1] + muls[i + j]*nums[n-j-1])\n",
    "                \n",
    "        return dp[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "\n",
    "        # hard题目 -- 动态规划解法出现的频率相对高点\n",
    "        # 最后的结果 -- 开头取i(0-m)个,末尾取j=m-i个 dp[i][j]\n",
    "        n,m = len(nums),len(multipliers)\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            dp[0][i] = dp[0][i-1]+nums[n-i]*multipliers[i-1]\n",
    "            dp[i][0] = dp[i-1][0]+nums[i-1]*multipliers[i-1]\n",
    "        res = max(dp[0][m],dp[m][0])\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for k in range(i+1,m+1):\n",
    "                dp[i][k-i] = max(dp[i-1][k-i]+nums[i-1]*multipliers[k-1],dp[i][k-i-1]+nums[n-(k-i)]*multipliers[k-1])\n",
    "                if k == m:res = max(res,dp[i][k-i])\n",
    "        return res\n",
    "\n",
    "        # 深度优先搜索 -- 终止条件\n",
    "        # 由于mn规模过大,dfs超时 -- 本题使用动态规划！\n",
    "        # n,m = len(nums),len(multipliers)\n",
    "        # res = []\n",
    "        # def dfs(arr,count,total):\n",
    "        #     if count == m:\n",
    "        #         res.append(total)\n",
    "        #         return \n",
    "        #     if arr[0] == arr[-1]:\n",
    "        #         dfs([],count+1,total+arr[0]*multipliers[-1])\n",
    "        #     else:\n",
    "        #         tmp = [[0,len(arr)-1,-1],[1,len(arr),0]]\n",
    "        #         for i,j,k in tmp:\n",
    "        #             dfs(arr[i:j],count+1,total+arr[k]*multipliers[count])\n",
    "        #     return    \n",
    "        # dfs(nums,0,0)\n",
    "        # return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        \n",
    "    \n",
    "\n",
    "        n,m = len(nums), len(multipliers)\n",
    "        dp=[[0]*(m+1) for _ in range(m+1)]\n",
    "        # dp[i][j] - max score after using i numbers on left and j numbers on the right\n",
    "        res=float(\"-inf\")\n",
    "        for i in range(m+1):\n",
    "            for j in range(m-i+1):\n",
    "                if i+j==0:\n",
    "                    continue\n",
    "                    \n",
    "                if i==0:\n",
    "                    dp[i][j] = dp[i][j-1]+multipliers[j-1]*nums[n-j]\n",
    "                elif j==0:\n",
    "                    dp[i][j] = dp[i-1][j]+multipliers[i-1]*nums[i-1]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1]+multipliers[i+j-1]*nums[n-j],\n",
    "                                    dp[i-1][j]+multipliers[i+j-1]*nums[i-1])\n",
    "                if i+j==m:\n",
    "                    res = max(res, dp[i][j])\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        return res\n",
    "                \n",
    "\n",
    "#   i     i+l<=n-l\n",
    "# 0123456789\n",
    "# start-0+n-j\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        f = [[0]*(m+1) for _ in range(m+1)]\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(m-i-1,-1,-1):\n",
    "                f[i][j] = max(multipliers[i+j]*nums[i] + f[i+1][j],\n",
    "                            multipliers[i+j]*nums[n-j-1] + f[i][j+1])\n",
    "        return f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(multipliers)\n",
    "        dp = [[0] * (m + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            # print(i)\n",
    "            dp[i][i] = dp[i-1][i-1] + nums[n - i] * multipliers[i-1]\n",
    "            dp[i][0] = dp[i-1][0] + nums[i - 1] * multipliers[i - 1]\n",
    "            for j in range(1, i):\n",
    "                dp[i][j] = max(dp[i-1][j] + nums[i - j - 1] * multipliers[i - 1], dp[i-1][j-1] + nums[n - j] * multipliers[i - 1])\n",
    "        return max(dp[m])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], muls: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(muls)\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "        ans = float('-inf')\n",
    "        for k in range(1, m+1):\n",
    "            for i in range(0, k+1):\n",
    "                if i == 0:\n",
    "                    dp[i][k-i] = dp[i][k-i-1] + nums[n-k+i]*muls[k-1]\n",
    "                elif i == k:\n",
    "                    dp[i][k-i] = dp[i-1][k-i] + nums[i-1]*muls[k-1]\n",
    "                else:\n",
    "                    dp[i][k-i] = max(dp[i][k-i-1] + nums[n-k+i]*muls[k-1], dp[i-1][k-i] + nums[i-1]*muls[k-1])\n",
    "                if (k == m):\n",
    "                    ans = max(ans, dp[i][k-i])    \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(multipliers)\n",
    "        f = [[-10 ** 9] * (m + 1) for _ in range(m + 1)]\n",
    "        f[1][1] = nums[0] * multipliers[0]\n",
    "        f[1][0] = nums[n - 1] * multipliers[0]\n",
    "        for i in range(1, m):\n",
    "            f[i + 1][0] = f[i][0] + multipliers[i] * nums[n - i - 1]\n",
    "            f[i + 1][i + 1] = f[i][i] + multipliers[i] * nums[i]\n",
    "            for j in range(1, i + 1):\n",
    "                f[i + 1][j] = max(f[i + 1][j], f[i][j] + multipliers[i] * nums[n - i - 1 + j])\n",
    "                f[i + 1][j] = max(f[i + 1][j], f[i][j - 1] + multipliers[i] * nums[j - 1])\n",
    "        return max(x for x in f[m])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        muls = multipliers\n",
    "        m = len(muls)\n",
    "        dp = [[0] * (m+1) for _ in range(m+1)]\n",
    "        ans = float('-inf')\n",
    "        for k in range(1, m+1):\n",
    "            for i in range(0, k+1):\n",
    "                if i == 0:\n",
    "                    dp[i][k-i] = dp[i][k-i-1] + nums[n-k+i] * muls[k-1]\n",
    "                elif i == k:\n",
    "                    dp[i][k-i] = dp[i-1][k-i] + nums[i-1] * muls[k-1]\n",
    "                else:\n",
    "                    dp[i][k-i] = max(dp[i][k-i-1] + nums[n-k+i]*muls[k-1], dp[i-1][k-i] + nums[i-1] * muls[k-1])\n",
    "                if (k == m):\n",
    "                    ans = max(ans, dp[i][k-i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], muls: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(muls)\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(m-i-1, -1, -1):\n",
    "                dp[i][j] = max(dp[i+1][j] + muls[i + j]*nums[i], dp[i][j+1] + muls[i + j]*nums[n-j-1])\n",
    "                \n",
    "        return dp[0][0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        f = [[0]*(m+1) for _ in range(m+1)]\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(m-i-1,-1,-1):\n",
    "                f[i][j] = max(multipliers[i+j]*nums[i] + f[i+1][j],\n",
    "                            multipliers[i+j]*nums[n-j-1] + f[i][j+1])\n",
    "        return f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        dp = [[0] * (m + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(i + 1):\n",
    "                k = i - j\n",
    "                dp[j][k] = max(dp[j + 1][k] + nums[j] * multipliers[i], dp[j][k + 1] + nums[n - 1 - k] * multipliers[i])\n",
    "\n",
    "        return dp[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], muls: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(muls)\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "        ans = float('-inf')\n",
    "        for k in range(1, m+1):\n",
    "            for i in range(0, k+1):\n",
    "                if i == 0:\n",
    "                    dp[i][k-i] = dp[i][k-i-1] + nums[n-k+i]*muls[k-1]\n",
    "                elif i == k:\n",
    "                    dp[i][k-i] = dp[i-1][k-i] + nums[i-1]*muls[k-1]\n",
    "                else:\n",
    "                    dp[i][k-i] = max(dp[i][k-i-1] + nums[n-k+i]*muls[k-1], dp[i-1][k-i] + nums[i-1]*muls[k-1])\n",
    "                if (k == m):\n",
    "                    ans = max(ans, dp[i][k-i])    \n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n,m = len(nums), len(multipliers)\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "        for k in range(1,m+1):\n",
    "            for i in range(0,k+1):\n",
    "                l,r = i,k-i\n",
    "                if l==0:\n",
    "                    dp[l][r] = nums[n-r]*multipliers[k-1] + dp[l][r-1]\n",
    "                elif r==0:\n",
    "                    dp[l][r] = nums[l-1]*multipliers[k-1] + dp[l-1][r]\n",
    "                else:\n",
    "                    dp[l][r] = max(nums[l-1]*multipliers[k-1]+dp[l-1][r],\\\n",
    "                                    nums[n-r]*multipliers[k-1]+dp[l][r-1])\n",
    "        \n",
    "        max_res = -float('inf')\n",
    "        for i in range(0,m+1):\n",
    "            max_res = max(max_res, dp[i][m-i])\n",
    "        return max_res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], muls: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(muls)\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "        ans = float('-inf')\n",
    "        for k in range(1, m+1):\n",
    "            for i in range(0, k+1):\n",
    "                if i == 0:\n",
    "                    dp[i][k-i] = dp[i][k-i-1] + nums[n-k+i]*muls[k-1]\n",
    "                elif i == k:\n",
    "                    dp[i][k-i] = dp[i-1][k-i] + nums[i-1]*muls[k-1]\n",
    "                else:\n",
    "                    dp[i][k-i] = max(dp[i][k-i-1] + nums[n-k+i]*muls[k-1], dp[i-1][k-i] + nums[i-1]*muls[k-1])\n",
    "                if (k == m):\n",
    "                    ans = max(ans, dp[i][k-i])    \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(multipliers)\n",
    "        #dp[i][j] 开头选i个 末尾选j个 最大分数\n",
    "        dp = [[0] * (m + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = 0\n",
    "        ans = -inf\n",
    "        for k in range(1,m + 1):\n",
    "            mul = multipliers[k - 1]\n",
    "            dp[0][k] = dp[0][k - 1] + nums[-k] * mul\n",
    "            dp[k][0] = dp[k - 1][0] + nums[k - 1] * mul\n",
    "            for i in range(1,k):\n",
    "                res1 = dp[i - 1][k - i] + nums[i - 1] * mul\n",
    "                res2 = dp[i][k - i - 1] + nums[-(k - i)] * mul\n",
    "                dp[i][k - i] = max(res1,res2)\n",
    "                if k == m:\n",
    "                    ans = max(ans,dp[i][k - i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        m,n = len(nums), len(multipliers)\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        res = float('-inf')\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0] = dp[i-1][0] + nums[i-1]*multipliers[i-1]\n",
    "        for i in range(1,n+1):\n",
    "            dp[0][i] = dp[0][i-1] + nums[m-i]*multipliers[i-1]\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                if i + j > n:\n",
    "                    break\n",
    "                dp[i][j] = max(dp[i-1][j]+nums[i-1]*multipliers[i+j-1],dp[i][j-1]+nums[m-j]*multipliers[i+j-1])\n",
    "                if i+j == n:\n",
    "                    res = max(res, dp[i][j])\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n,m = len(nums),len(multipliers)\n",
    "        # @cache\n",
    "        # def dfs(i,j,k):\n",
    "        #     if k == m:\n",
    "        #         return 0\n",
    "        #     if i > j:\n",
    "        #         return 0\n",
    "        #     ans = nums[i]*multipliers[k] + dfs(i + 1,j,k + 1)\n",
    "        #     return max(ans,nums[j]*multipliers[k] + dfs(i,j - 1,k + 1))\n",
    "        \n",
    "        # return dfs(0,n - 1,0)\n",
    "        dp = [[0 for _ in range(m + 1)] for _ in range(m + 1)] \n",
    "        res = -inf\n",
    "        for k in range(1,m + 1):\n",
    "            for i in range(k + 1):\n",
    "                j = k - i\n",
    "                if i == 0:\n",
    "                    dp[i][j] = dp[i][j - 1] + nums[-k]*multipliers[k - 1]\n",
    "                elif i == k:\n",
    "                    dp[i][j] = dp[i - 1][j] + nums[i - 1]*multipliers[k - 1]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j] + nums[i - 1]*multipliers[k - 1],dp[i][j - 1] + nums[-j]*multipliers[k - 1])\n",
    "                if k == m:\n",
    "                    res = max(res,dp[i][j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], mul: List[int]) -> int:\n",
    "        n,m=len(nums),len(mul)\n",
    "        dp=[[float('-inf')]*(m+1) for _ in range(m+1)]\n",
    "        dp[0][0]=0\n",
    "        res=float('-inf')\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(i + 1):\n",
    "                l, r = j, i - j\n",
    "                if l:\n",
    "                    dp[l][r]=max(dp[l][r], dp[l-1][r] + nums[l-1] * mul[i-1])\n",
    "                if r:\n",
    "                    dp[l][r]=max(dp[l][r], dp[l][r-1] + nums[-r] * mul[i-1])\n",
    "                if i==m:\n",
    "                    res=max(res,dp[l][r])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        # 初始化动态规划数组\n",
    "        dp = [[float('-inf')] * (m+1) for _ in range(m+1)]\n",
    "        dp[0][0] = 0\n",
    "        \n",
    "        for i in range(m+1):\n",
    "            for j in range(m+1-i):\n",
    "                if i > 0:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j] + nums[i-1] * multipliers[i+j-1])\n",
    "                if j > 0:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][j-1] + nums[-j] * multipliers[i+j-1])\n",
    "        \n",
    "        return max(dp[i][m-i] for i in range(m+1))\n",
    "\n",
    "# 示例\n",
    "nums = [1, 2, 3]\n",
    "multipliers = [3, 2, 1]\n",
    "sol = Solution()\n",
    "print(sol.maximumScore(nums, multipliers))  # 输出应为 14\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        m = len(multipliers)\n",
    "        n = len(nums)\n",
    "\n",
    "        dp = [[0 for _ in range(m+1)] for _ in range(m+1)]\n",
    "\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = dp[i-1][0] + nums[i-1]*multipliers[i-1]\n",
    "\n",
    "        for j in range(1, m+1):\n",
    "            dp[0][j] = dp[0][j-1] + nums[n-j]*multipliers[j-1]\n",
    "        \n",
    "        res = float(\"-inf\")\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, m+1):\n",
    "                if i+j <= m:\n",
    "                    # for k in range(min(i,j)+1):\n",
    "                        dp[i][j] = max(dp[i][j-1]+nums[n-j]*multipliers[i+j-1], dp[i-1][j]+nums[i-1]*multipliers[i+j-1])\n",
    "                        # dp[i][j] = max(dp[i][j], dp[i][j-1]+nums[n-j]*multipliers[i+j-1])\n",
    "\n",
    "        for i in range(m+1):\n",
    "            res = max(res, dp[i][m-i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        m = len(multipliers)\n",
    "        n = len(nums)\n",
    "        res = float('-inf')\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "        for k in range(1, m+1):\n",
    "            for i in range(k+1):\n",
    "                if i == 0:\n",
    "                    dp[i][k-i] = dp[i][k-i-1] + nums[n-k+i]*multipliers[k-1]\n",
    "                elif i == k:\n",
    "                    dp[i][k-i] = dp[i-1][k-i] + nums[i-1]*multipliers[k-1]\n",
    "                else:\n",
    "                    dp[i][k-i] = max(dp[i][k-i-1] + nums[n-k+i]*multipliers[k-1], dp[i-1][k-i] + nums[i-1]*multipliers[k-1])\n",
    "                if k == m:\n",
    "                    res = max(res, dp[i][k-i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        m = len(multipliers)\n",
    "        n = len(nums)\n",
    "\n",
    "        dp = [[0 for _ in range(m+1)] for _ in range(m+1)]\n",
    "\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = dp[i-1][0] + nums[i-1]*multipliers[i-1]\n",
    "\n",
    "        for j in range(1, m+1):\n",
    "            dp[0][j] = dp[0][j-1] + nums[n-j]*multipliers[j-1]\n",
    "        \n",
    "        res = float(\"-inf\")\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, m+1):\n",
    "                if i+j <= m:\n",
    "                    # for k in range(min(i,j)+1):\n",
    "                        dp[i][j] = max(dp[i][j-1]+nums[n-j]*multipliers[i+j-1], dp[i-1][j]+nums[i-1]*multipliers[i+j-1])\n",
    "                        # dp[i][j] = max(dp[i][j], dp[i][j-1]+nums[n-j]*multipliers[i+j-1])\n",
    "\n",
    "        for i in range(m+1):\n",
    "            res = max(res, dp[i][m-i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "\n",
    "        m=len(multipliers)\n",
    "        dp=[[0 for i in range(m+1)] for j in range(m+1)]\n",
    "        ans=-inf \n",
    "        for i in range(m+1):\n",
    "            for j in range(m+1):\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j]=0\n",
    "                elif i==0 and j!=0:\n",
    "                    dp[i][j]=dp[i][j-1]+multipliers[j-1]*nums[-j]\n",
    "                elif i!=0 and j==0:\n",
    "                    dp[i][j]=dp[i-1][j]+multipliers[i-1]*nums[i-1]\n",
    "                else:\n",
    "                    if i+j<=m:\n",
    "                        dp[i][j]=max(dp[i-1][j]+multipliers[i+j-1]*nums[i-1],dp[i][j-1]+multipliers[i+j-1]*nums[-j])\n",
    "                if i+j==m:\n",
    "                    ans=max(dp[i][j],ans)\n",
    "        # for i in dp:\n",
    "        #     print(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(multipliers)\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        for now in range(n-1, -1, -1):\n",
    "            for choose in range(n-1, -1, -1):\n",
    "                dp[now][choose] = max(\n",
    "                    multipliers[now]*nums[choose] + dp[now+1][choose+1],\n",
    "                    multipliers[now]*nums[choose-now-1] + dp[now+1][choose]\n",
    "                )\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        ans=-inf\n",
    "        m=len(multipliers)\n",
    "        dp=[[-inf for i in range(m+1)] for j in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            for j in range(m+1):\n",
    "                if i+j>m:\n",
    "                    break\n",
    "                dx=i+j-1\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j]=0\n",
    "                elif i==0 and j!=0:\n",
    "                    dp[i][j]=dp[i][j-1]+nums[-j]*multipliers[dx]\n",
    "                elif j==0 and i!=0:\n",
    "                    \n",
    "                    dp[i][j]=dp[i-1][j]+nums[i-1]*multipliers[dx]\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j]+nums[i-1]*multipliers[dx],dp[i][j-1]+nums[-j]*multipliers[dx])\n",
    "                if i+j==m:\n",
    "                    ans=max(ans,dp[i][j])\n",
    "        # for i in dp:\n",
    "        #     print(i)                    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        dp = [[0 for _j in range(1005)] for _i in range(1005)]\n",
    "        rst = float('-inf')\n",
    "        for k in range(1, m + 1):\n",
    "            for i in range(k + 1):\n",
    "                if i == 0:\n",
    "                    dp[i][k - i] = dp[i][k - i - 1] + nums[n - k + i] * multipliers[k - 1]\n",
    "                elif i == k:\n",
    "                    dp[i][k - i] = dp[i - 1][k - i] + nums[i - 1] * multipliers[k - 1]\n",
    "                else:\n",
    "                    dp[i][k - i] = max(dp[i][k - i - 1] + nums[n - k + i] * multipliers[k - 1],\n",
    "                                       dp[i - 1][k - i] + nums[i - 1] * multipliers[k - 1])\n",
    "                if k == m:\n",
    "                    rst = max(rst, dp[i][k - i])\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        \n",
    "        dp = [[0 for _ in range(1005)] for _ in range(1005)] \n",
    "\n",
    "        res = -0x3f3f3f3f\n",
    "\n",
    "        for k in range(1, m + 1):       #取的总个数\n",
    "            for i in range(0, k + 1):   #左边取的个数\n",
    "                j = k - i               #右边取的个数\n",
    "                if i == 0:              #都是从右边取的\n",
    "                    dp[i][j] = dp[i][j-1] + nums[-k] * multipliers[k-1]\n",
    "                elif i == k:            #都是从左边取的\n",
    "                    dp[i][j] = dp[i-1][j] + nums[k-1] * multipliers[k-1]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j] + nums[i-1]*multipliers[k-1],  dp[i][j-1] + nums[-j] * multipliers[k-1])\n",
    "                if k == m:\n",
    "                    res = max(res, dp[i][j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(multipliers)\n",
    "        f = [[[-10 ** 9, -10 ** 9] for i in range(m + 1)] for _ in range(m + 1)]\n",
    "        f[1][1][1] = nums[0] * multipliers[0]\n",
    "        f[1][0][0] = nums[n - 1] * multipliers[0]\n",
    "        for i in range(1, m):\n",
    "            f[i + 1][0][0] = f[i][0][0] + multipliers[i] * nums[n - i - 1]\n",
    "            f[i + 1][i + 1][1] = f[i][i][1] + multipliers[i] * nums[i]\n",
    "            for j in range(1, i + 1):\n",
    "                f[i + 1][j][0] = max(f[i + 1][j][0], max(f[i][j][0], f[i][j][1]) + multipliers[i] * nums[n - i - 1 + j])\n",
    "                f[i + 1][j][1] = max(f[i + 1][j][1], max(f[i][j - 1][0], f[i][j - 1][1]) + multipliers[i] * nums[j - 1])\n",
    "        ret = -10 ** 9\n",
    "        for x in f[m]:\n",
    "            for y in x:\n",
    "                ret = max(ret, y)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n,m=len(nums),len(multipliers)\n",
    "        dp=[[0]*(m+1) for i in range(m+1)]\n",
    "        res=-np.inf\n",
    "        for k in range(1,m+1):\n",
    "            for i in range(0,k+1):\n",
    "                j=k-i\n",
    "                if i==0:\n",
    "                    dp[i][j]=dp[i][j-1]+nums[-k]*multipliers[k-1]\n",
    "                elif i==k:\n",
    "                    dp[i][j]=dp[i-1][j]+nums[k-1]*multipliers[k-1]\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j]+nums[i-1]*multipliers[k-1],dp[i][j-1]+nums[-j]*multipliers[k-1])\n",
    "                if k==m:\n",
    "                    res=max(res,dp[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        @lru_cache(len(multipliers))\n",
    "        def dfs(left, right, idx) -> int:\n",
    "            if idx >= len(multipliers):\n",
    "                return 0\n",
    "            multiplier = multipliers[idx]\n",
    "            idx += 1\n",
    "            return max(nums[left] * multiplier + dfs(left + 1, right, idx),\n",
    "                       nums[right] * multiplier + dfs(left, right - 1, idx))\n",
    "\n",
    "        return dfs(0, len(nums) - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore1(self, nums: List[int], muls: List[int]) -> int:\n",
    "        n, m = len(nums), len(muls)\n",
    "        \n",
    "        @cache\n",
    "        def help(beg: int, end: int, i: int) -> int:\n",
    "            if i == m: return 0\n",
    "            return max(nums[beg] * muls[i] + help(beg + 1, end, i + 1), nums[end] * muls[i] + help(beg, end - 1, i + 1))\n",
    "\n",
    "        ans = help(0, n - 1, 0)\n",
    "        \n",
    "        del help\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "    def maximumScore(self, nums: List[int], muls: List[int]) -> int:\n",
    "        import gc\n",
    "        n, m = len(nums), len(muls)\n",
    "        \n",
    "        @cache\n",
    "        def help(beg: int, end: int, i: int) -> int:\n",
    "            if i == m: return 0\n",
    "            return max(nums[beg] * muls[i] + help(beg + 1, end, i + 1), nums[end] * muls[i] + help(beg, end - 1, i + 1))\n",
    "\n",
    "        ans = help(0, n - 1, 0)\n",
    "        \n",
    "        gc.collect()\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        k = len(multipliers)\n",
    "        dp = [[0]*k*2 for _ in range(k)]\n",
    "\n",
    "        dp[0][0] = nums[0]*multipliers[0]\n",
    "        dp[0][-1] = nums[-1]*multipliers[0]\n",
    "\n",
    "        for i in range(1, k):\n",
    "            for j in range(i+1):\n",
    "                dp[i][j] = nums[j]*multipliers[i] + max(dp[i-1][j-1] if j-1>=0 else -np.inf, dp[i-1][j-i] if j-i<0 else -np.inf)\n",
    "\n",
    "            for j in range(-i-1, 0):\n",
    "                dp[i][j] = nums[j]*multipliers[i] + max(dp[i-1][j+1] if j+1<0 else -np.inf, dp[i-1][i+j] if i+j>=0 else -np.inf)\n",
    "\n",
    "        return max(-np.inf, *dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        @cache\n",
    "        def f(l,r):\n",
    "            indx = n-r+l-1\n",
    "            if indx == m:\n",
    "                return 0\n",
    "            return max(nums[l]*multipliers[indx] + f(l+1,r), nums[r]*multipliers[indx] + f(l,r-1))\n",
    "        res = f(0,n-1)\n",
    "        f.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums, multipliers):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type multipliers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # max_res = 0\n",
    "        # # 记忆化搜索\n",
    "        # def dfs(i, size, nums_new, multipliers, sum_):\n",
    "        #     global max_res\n",
    "        #     if i == size:\n",
    "        #         return\n",
    "        #     n = len(nums_new)\n",
    "\n",
    "        #     head_n_tail = [0, n-1]\n",
    "        #     for j in head_n_tail:\n",
    "        #         if j == 0:\n",
    "        #             sum_ += multipliers[j]*nums_new[0]\n",
    "        #             nums_new = nums_new[1:]\n",
    "        #             # global max_res\n",
    "        #             max_res = max(max_res, sum_)\n",
    "        #             dfs(i+1, size, nums_new, multipliers, sum_)\n",
    "                    \n",
    "        #         if j == n-1:\n",
    "        #             sum_ += multipliers[j]*nums_new[n-1]\n",
    "        #             nums_new = nums_new[:n-1]\n",
    "        #             # global max_res\n",
    "        #             max_res = max(max_res, sum_)\n",
    "        #             dfs(i+1, size, nums_new, multipliers, sum_)\n",
    "\n",
    "        \n",
    "        # dfs(0, len(nums), nums, multipliers, 0)\n",
    "        # return max_res\n",
    "        @cache\n",
    "        def dfs(i, left, right):\n",
    "            if i == len(multipliers):\n",
    "                return 0\n",
    "            # 选择左端或右端的数字，并计算分数\n",
    "            left_score = multipliers[i] * nums[left] + dfs(i + 1, left + 1, right)\n",
    "            right_score = multipliers[i] * nums[right] + dfs(i + 1, left, right - 1)\n",
    "            return max(left_score, right_score)\n",
    "\n",
    "        max_score = dfs(0, 0, len(nums) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums, multipliers):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type multipliers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_res = [0]\n",
    "        # 记忆化搜索\n",
    "        # @cache  \n",
    "        # def dfs(i, size, nums_new, multipliers, sum_, max_res):\n",
    "        #     if i == len(multipliers):\n",
    "        #         return\n",
    "        #     n = len(nums_new)\n",
    "        #     head_n_tail = [0, n-1]\n",
    "        #     for j in head_n_tail:\n",
    "        #         if j == 0:\n",
    "        #             max_res[0] = max(max_res[0], sum_ + multipliers[i]*nums_new[0])\n",
    "        #             print(\"aaa:\", i, \"sum:\", sum_, \"max:\", max_res[0])\n",
    "        #             dfs(i+1, size, nums_new[1:], multipliers, sum_ + multipliers[i]*nums_new[0], max_res)\n",
    "                   \n",
    "        #         elif j == n-1:\n",
    "        #             max_res[0] = max(max_res[0], sum_ + multipliers[i]*nums_new[-1])\n",
    "        #             print(\"bbb:\", i, \"sum:\", sum_, \"max:\", max_res[0])\n",
    "        #             dfs(i+1, size, nums_new[:-1], multipliers, sum_ + multipliers[i]*nums_new[-1], max_res)\n",
    "\n",
    "        # dfs(0, len(multipliers), nums, multipliers, 0, max_res)\n",
    "        # dfs.cache_clear()\n",
    "        # return max_res[0]\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, left, right):\n",
    "            if i == len(multipliers):\n",
    "                return 0\n",
    "            # 选择左端或右端的数字，并计算分数\n",
    "            left_score = multipliers[i] * nums[left] + dfs(i + 1, left + 1, right)\n",
    "            right_score = multipliers[i] * nums[right] + dfs(i + 1, left, right - 1)\n",
    "            return max(left_score, right_score)\n",
    "\n",
    "        max_score = dfs(0, 0, len(nums) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        m, n = len(multipliers), len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, l, r):\n",
    "            if idx == m:\n",
    "                return 0\n",
    "            \n",
    "            return max(multipliers[idx] * nums[l] + dfs(idx + 1, l + 1, r), multipliers[idx] * nums[r] + dfs(idx + 1, l, r - 1))\n",
    "        \n",
    "        ans = dfs(0, 0, n -1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums, multipliers):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type multipliers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_res = [0]\n",
    "        # 记忆化搜索\n",
    "        # @cache  \n",
    "        # def dfs(i, size, nums_new, multipliers, sum_, max_res):\n",
    "        #     if i == len(multipliers):\n",
    "        #         return\n",
    "        #     n = len(nums_new)\n",
    "        #     head_n_tail = [0, n-1]\n",
    "        #     for j in head_n_tail:\n",
    "        #         if j == 0:\n",
    "        #             max_res[0] = max(max_res[0], sum_ + multipliers[i]*nums_new[0])\n",
    "        #             print(\"aaa:\", i, \"sum:\", sum_, \"max:\", max_res[0])\n",
    "        #             dfs(i+1, size, nums_new[1:], multipliers, sum_ + multipliers[i]*nums_new[0], max_res)\n",
    "                   \n",
    "        #         elif j == n-1:\n",
    "        #             max_res[0] = max(max_res[0], sum_ + multipliers[i]*nums_new[-1])\n",
    "        #             print(\"bbb:\", i, \"sum:\", sum_, \"max:\", max_res[0])\n",
    "        #             dfs(i+1, size, nums_new[:-1], multipliers, sum_ + multipliers[i]*nums_new[-1], max_res)\n",
    "\n",
    "        # dfs(0, len(multipliers), nums, multipliers, 0, max_res)\n",
    "        # dfs.cache_clear()\n",
    "        # return max_res[0]\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, left, right):\n",
    "            if i == len(multipliers):\n",
    "                return 0\n",
    "            # 选择左端或右端的数字，并计算分数\n",
    "            left_score = multipliers[i] * nums[left] + dfs(i + 1, left + 1, right)\n",
    "            right_score = multipliers[i] * nums[right] + dfs(i + 1, left, right - 1)\n",
    "            return max(left_score, right_score)\n",
    "\n",
    "        max_score = dfs(0, 0, len(nums) - 1)\n",
    "        dfs.cache_clear()\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        m = len(multipliers)\n",
    "        @cache\n",
    "        def dfs(l:int, r:int, k:int)->int:\n",
    "            if k == m:\n",
    "                return 0\n",
    "            \n",
    "            return max(dfs(l+1,r,k+1) + nums[l]*multipliers[k], \\\n",
    "                       dfs(l,r-1,k+1) + nums[r]*multipliers[k],)\n",
    "\n",
    "        ans = dfs(0,len(nums)-1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n,m = len(nums),len(multipliers)\n",
    "        @lru_cache(None)\n",
    "        def traversal(i,j,idx):\n",
    "            if idx==m: return 0\n",
    "            r1 = multipliers[idx]*nums[i]+traversal(i+1,j,idx+1)\n",
    "            r2 = multipliers[idx]*nums[j]+traversal(i,j-1,idx+1)\n",
    "            return max(r1,r2)\n",
    "        res = traversal(0,n-1,0)\n",
    "        traversal.cache_clear()\n",
    "        return  res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i + j >= m:\n",
    "                return 0\n",
    "            return max(f(i+1, j) + multipliers[i+j] * nums[i], f(i, j+1) + multipliers[i+j] * nums[~j])\n",
    "        \n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "       n = len(nums)\n",
    "       m = len(multipliers)\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i + j >= m:\n",
    "             return 0\n",
    "          return max(dfs(i + 1, j) + multipliers[i + j] * nums[i], dfs(i, j + 1) + multipliers[i + j] * nums[n - j - 1])\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(multipliers)\n",
    "        @cache\n",
    "        def fun(now, choose):\n",
    "            if now == n:\n",
    "                return 0\n",
    "            return max(\n",
    "                multipliers[now]*nums[choose] + fun(now+1, choose+1),\n",
    "                multipliers[now]*nums[choose-now-1] + fun(now+1, choose)\n",
    "            )\n",
    "        return fun(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == m: return 0\n",
    "            #n - i\n",
    "            x = multipliers[i]\n",
    "            return max(x * nums[j] + dfs(i + 1, j + 1), x * nums[n - i + j - 1] + dfs(i + 1, j))\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(multipliers)\n",
    "        @cache\n",
    "        def dfs(idx,L,R) -> int:\n",
    "            op = multipliers[idx]\n",
    "            if idx == m - 1:\n",
    "                return max(op * nums[L],op * nums[R])\n",
    "            res1 = op * nums[L] + dfs(idx + 1,L + 1,R)\n",
    "            res2 = op * nums[R] + dfs(idx + 1,L,R - 1)\n",
    "            return max(res1,res2)\n",
    "        return dfs(0,0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        mNum = len(multipliers)\n",
    "        @cache\n",
    "        def dfs(i, j, mIndex):\n",
    "            multiplier = multipliers[mIndex]\n",
    "            if mIndex == mNum-1:\n",
    "                return max(multiplier*nums[i], multiplier*nums[j])\n",
    "            leftScore = nums[i]\n",
    "            maxScore = leftScore*multiplier+dfs(i+1, j, mIndex+1)\n",
    "            rightScore = nums[j]\n",
    "            maxScore = max(maxScore, rightScore*multiplier+dfs(i, j-1, mIndex+1))\n",
    "            return maxScore\n",
    "        return dfs(0, len(nums)-1, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: List[int], b: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        m = len(b)\n",
    "        @cache \n",
    "        def f(i, j):\n",
    "            if n-(j-i+1)==m:\n",
    "                return 0 \n",
    "            else:\n",
    "                ix = n-(j-i+1)\n",
    "                return max(f(i+1, j) + b[ix]*a[i], f(i, j-1) + b[ix]*a[j]) \n",
    "        return f(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(multipliers)\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            i = n-(r-l+1)\n",
    "            if i == m:\n",
    "                return 0\n",
    "            \n",
    "            res = dfs(l+1, r) + nums[l]*multipliers[i]\n",
    "            res = max(res, dfs(l, r-1) + nums[r]*multipliers[i])\n",
    "            return res \n",
    "        \n",
    "        return dfs(0, n-1)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        @cache\n",
    "        def f(l,r):\n",
    "            indx = n-r+l-1\n",
    "            if indx == m:\n",
    "                return 0\n",
    "            return max(nums[l]*multipliers[indx] + f(l+1,r), nums[r]*multipliers[indx] + f(l,r-1))\n",
    "        return f(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def max_(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def min_(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(multipliers)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            ind = i+(n-1-j)\n",
    "            if ind == m:\n",
    "                return 0\n",
    "            return max_(dfs(i+1, j)+nums[i]*multipliers[ind], dfs(i, j-1)+nums[j]*multipliers[ind])\n",
    "        \n",
    "        return dfs(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(multipliers)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            ind = i+(n-1-j)\n",
    "            if ind == m:\n",
    "                return 0\n",
    "            a, b = dfs(i+1, j)+nums[i]*multipliers[ind], dfs(i, j-1)+nums[j]*multipliers[ind]\n",
    "            return a if a > b else b\n",
    "        \n",
    "        return dfs(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n, m = len(nums), len(multipliers)\n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            if i == m: return 0\n",
    "            return max(dfs(i + 1, j + 1, k) + nums[j] * multipliers[i], dfs(i + 1, j, k - 1) + multipliers[i] * nums[k])\n",
    "        return dfs(0, 0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "\n",
    "        n, m = len(nums), len(multipliers)\n",
    "\n",
    "        @cache\n",
    "        def dfs(l, r, cnt):\n",
    "            if cnt >= m:\n",
    "                return 0\n",
    "            res = max(dfs(l + 1, r, cnt + 1) + multipliers[cnt] * nums[l], dfs(l, r - 1, cnt + 1) + multipliers[cnt] * nums[r])\n",
    "            return res\n",
    "        return dfs(0, n - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        m = len(multipliers)\n",
    "        @cache\n",
    "        def dfs(l:int, r:int, k:int)->int:\n",
    "            if k == m:\n",
    "                return 0\n",
    "            \n",
    "            return max(dfs(l+1,r,k+1) + nums[l]*multipliers[k], \\\n",
    "                       dfs(l,r-1,k+1) + nums[r]*multipliers[k],)\n",
    "\n",
    "\n",
    "        return dfs(0,len(nums)-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums, multipliers):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type multipliers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_res = [0]\n",
    "        # 记忆化搜索\n",
    "        # @cache  \n",
    "        # def dfs(i, size, nums_new, multipliers, sum_, max_res):\n",
    "        #     if i == len(multipliers):\n",
    "        #         return\n",
    "        #     n = len(nums_new)\n",
    "        #     head_n_tail = [0, n-1]\n",
    "        #     for j in head_n_tail:\n",
    "        #         if j == 0:\n",
    "        #             max_res[0] = max(max_res[0], sum_ + multipliers[i]*nums_new[0])\n",
    "        #             print(\"aaa:\", i, \"sum:\", sum_, \"max:\", max_res[0])\n",
    "        #             dfs(i+1, size, nums_new[1:], multipliers, sum_ + multipliers[i]*nums_new[0], max_res)\n",
    "                   \n",
    "        #         elif j == n-1:\n",
    "        #             max_res[0] = max(max_res[0], sum_ + multipliers[i]*nums_new[-1])\n",
    "        #             print(\"bbb:\", i, \"sum:\", sum_, \"max:\", max_res[0])\n",
    "        #             dfs(i+1, size, nums_new[:-1], multipliers, sum_ + multipliers[i]*nums_new[-1], max_res)\n",
    "\n",
    "        # dfs(0, len(multipliers), nums, multipliers, 0, max_res)\n",
    "        # dfs.cache_clear()\n",
    "        # return max_res[0]\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, left, right):\n",
    "            if i == len(multipliers):\n",
    "                return 0\n",
    "            # 选择左端或右端的数字，并计算分数\n",
    "            left_score = multipliers[i] * nums[left] + dfs(i + 1, left + 1, right)\n",
    "            right_score = multipliers[i] * nums[right] + dfs(i + 1, left, right - 1)\n",
    "            return max(left_score, right_score)\n",
    "\n",
    "        max_score = dfs(0, 0, len(nums) - 1)\n",
    "        # dfs.cache_clear()\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], muls: List[int]) -> int:\n",
    "        n, m = len(nums), len(muls)\n",
    "        @cache\n",
    "        def help(beg: int, end: int, i: int) -> int:\n",
    "            if i == m: return 0\n",
    "            return max(nums[beg] * muls[i] + help(beg + 1, end, i + 1), nums[end] * muls[i] + help(beg, end - 1, i + 1))\n",
    "        \n",
    "        return help(0, n - 1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        n,m = len(nums),len(multipliers)\n",
    "        @cache\n",
    "        def traversal(i,j,idx):\n",
    "            if idx==m: return 0\n",
    "            r1 = multipliers[idx]*nums[i]+traversal(i+1,j,idx+1)\n",
    "            r2 = multipliers[idx]*nums[j]+traversal(i,j-1,idx+1)\n",
    "            return max(r1,r2)\n",
    "        return traversal(0,n-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        m = len(multipliers)\n",
    "        @cache\n",
    "        def dfs(i:int,j:int,deep:int)->int:\n",
    "            if deep == m:return 0\n",
    "            return max(nums[i]*multipliers[deep]+dfs(i+1, j, deep+1),nums[j]*multipliers[deep]+dfs(i, j-1, deep+1))\n",
    "        return dfs(0, n-1, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], muls: List[int]) -> int:\n",
    "        n, m = len(nums), len(muls)\n",
    "        @cache\n",
    "        def help(beg: int, end: int, i: int) -> int:\n",
    "            if i == m: return 0\n",
    "            return max(nums[beg] * muls[i] + help(beg + 1, end, i + 1), nums[end] * muls[i] + help(beg, end - 1, i + 1))\n",
    "        \n",
    "        return help(0, n - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        s = a + b + c\n",
    "        max_val = max(a, b, c)\n",
    "        return s - max_val if s < max_val * 2 else s // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        s = [a, b, c]\n",
    "        s.sort()\n",
    "        sroce = 0\n",
    "        while s[1]:\n",
    "            sroce += 1\n",
    "            s[1] -= 1\n",
    "            s[2] -= 1\n",
    "            s.sort()\n",
    "        return sroce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [a, b, c]\n",
    "        arr.sort()\n",
    "        cha = 0\n",
    "        while arr[1] != 0:\n",
    "            cha = arr[1] - arr[0]\n",
    "            if cha==0:\n",
    "                cha = 1\n",
    "            arr[1] -= cha\n",
    "            arr[2] -= cha\n",
    "            ans += cha\n",
    "            arr.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        return s - m if (s := a+b+c) < 2 * (m := max(a,b,c)) else s // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        s = a + b + c\n",
    "        m = max(a, b, c)\n",
    "        return min(s - m, m) if m > s >> 1 else s >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        sums = a + b + c\n",
    "        max_value = max(a, b, c)\n",
    "        if sums - max_value <= max_value:\n",
    "            return sums - max_value\n",
    "        else:\n",
    "            return sums // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [a, b, c]\n",
    "        arr.sort()\n",
    "        while arr[1] != 0:\n",
    "            arr[1] -= 1\n",
    "            arr[2] -= 1\n",
    "            ans += 1\n",
    "            arr.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        #找规律，贪心\n",
    "        #先整理成a<=b<=c的形式\n",
    "        #再分类讨论\n",
    "        if a>b: a,b=b,a\n",
    "        if c<a: a,b,c=c,a,b\n",
    "        elif a<c<b: b,c=c,b\n",
    "\n",
    "        if a+b<=c:\n",
    "            return a+b\n",
    "        else:\n",
    "            return (a+b+c)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        a,b,c = sorted([a,b,c])\n",
    "        if a+b <= c:\n",
    "            return (a+b)\n",
    "        else:\n",
    "            return (a+b+c)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        s = sorted((a, b, c))\n",
    "        ans = s[0]\n",
    "        if s[2]-s[1] >= s[0]:\n",
    "            ans += s[1]\n",
    "        else:\n",
    "            ans += (s[1]+s[2]-s[0])//2\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        lis=[a,b,c]\n",
    "        lis.sort()\n",
    "        a,b,c=lis[0],lis[1],lis[2]\n",
    "        if c>a+b:return a+b\n",
    "        elif c==a+b:return c\n",
    "        elif c<a+b:\n",
    "            if b==c:\n",
    "                if a%2==0:return (b-a)+sum(lis)//2\n",
    "                else:return (b-a)+3*(a-1)//2+1\n",
    "            else:\n",
    "                return sum(lis)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\r\n",
    "        if b < a:\r\n",
    "            a, b = b, a\r\n",
    "        if c < b:\r\n",
    "            b, c = c, b\r\n",
    "        if b < a:\r\n",
    "            a, b = b, a\r\n",
    "\r\n",
    "        if a + b <= c:\r\n",
    "            return(a + b)\r\n",
    "        else:\r\n",
    "            return(c + (a + b - c) // 2)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        ans = 0\n",
    "        nums = [-x for x in [a, b, c] if x]\n",
    "        heapify(nums)\n",
    "        while len(nums) >= 2:\n",
    "            x, y = heappop(nums), heappop(nums)\n",
    "            ans += 1\n",
    "            x += 1\n",
    "            y += 1\n",
    "            if x:\n",
    "                heappush(nums, x)\n",
    "            if y:\n",
    "                heappush(nums, y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        v = (a + b + c) // 2\n",
    "        m = max(a, b, c)\n",
    "        if m > v:\n",
    "            return min(a + b + c - m, m)\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        max_val = max(a, b, c)\n",
    "        sum_num = a + b + c\n",
    "        return sum_num - max_val if sum_num < max_val * 2 else sum_num // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        a, b, c = sorted([a, b, c])\n",
    "        if a + b >= c:\n",
    "            return (a + b + c) // 2\n",
    "        return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        sumx = a + b + c\n",
    "        if sumx - max(a, b, c) >= max(a, b, c):\n",
    "            return (sumx - 2 * max(a, b, c)) // 2 + max(a, b, c)\n",
    "        else:\n",
    "            return sumx - max(a, b, c)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\r\n",
    "        lis = [a, b, c]\r\n",
    "        lis.sort()\r\n",
    "        if lis[0] + lis[1] <= lis[2]:\r\n",
    "            return(lis[0] + lis[1])\r\n",
    "        else:\r\n",
    "            return(lis[2] + (lis[0] + lis[1] - lis[2]) // 2)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        t = a + b + c\n",
    "        c = max(a, b, c)\n",
    "        x = t - c\n",
    "        return x if x <= c else t // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        if max(a,b,c)*2<=a+b+c:\n",
    "            return (a+b+c)//2\n",
    "        else:\n",
    "            return a+b+c-max(a,b,c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        if a+b<=c:\n",
    "            return a+b\n",
    "        elif a+c<=b:\n",
    "            return a+c\n",
    "        elif b+c<=a:\n",
    "            return b+c\n",
    "        else:\n",
    "            return int((a+b+c)/2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        def myfunc(a:int,b:int,c:int):\n",
    "            m = [a,b,c]\n",
    "            m.sort()\n",
    "            return m\n",
    "        count = 0\n",
    "        while True:\n",
    "            a,b,c = myfunc(a,b,c)\n",
    "            if a + b < c:\n",
    "                return a+b+count\n",
    "            elif a + b == c:\n",
    "                return c+count\n",
    "            count += 1\n",
    "            a -= 1\n",
    "            c -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        l = [a, b, c]\n",
    "        s = sorted(l)\n",
    "\n",
    "        score = 0\n",
    "        while s[1] != 0:\n",
    "            s[1] = s[1] - 1\n",
    "            s[2] = s[2] - 1\n",
    "            score += 1\n",
    "            s = sorted(s)\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        ans = 0\n",
    "        t = [a, b, c]\n",
    "        while (t[0] != 0 or t[1] != 0) and (t[0] != 0 or t[2] != 0) and (t[1] != 0 or t[2] != 0):\n",
    "            idx = [0, 1, 2]\n",
    "            idx.sort(key=lambda x: t[x])\n",
    "            t[idx[2]] -= 1\n",
    "            if t[idx[0]] == 0:\n",
    "                t[idx[1]] -= 1\n",
    "            else:\n",
    "                t[idx[0]] -= 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        v = [a, b, c]\n",
    "        v.sort()\n",
    "        if v[0] + v[1] < v[2]:\n",
    "            return v[0] + v[1]\n",
    "        return v[0] + v[1] + v[2] >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        g = [a, b, c]\n",
    "        g.sort()\n",
    "        if g[0] + g[1] <= g[2]:\n",
    "            return g[0] + g[1]\n",
    "        return (a + b + c) // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        #找规律，贪心\n",
    "        if a>b: a,b=b,a\n",
    "        if c<a: a,b,c=c,a,b\n",
    "        elif a<c<b: b,c=c,b\n",
    "        if a+b<=c:\n",
    "            return a+b\n",
    "        else:\n",
    "            return (a+b+c)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        res = 0\n",
    "        x = min(a,b,c)\n",
    "        z = max(a,b,c)\n",
    "        y = a+b+c-x-z\n",
    "        diff = min(x, z - y)\n",
    "        res += diff\n",
    "        x -= diff\n",
    "        z -= diff\n",
    "        if x==0:\n",
    "            res += y\n",
    "        else:\n",
    "            if x%2==0:\n",
    "                res += x\n",
    "                y -= (x//2)\n",
    "                z -= (x//2)\n",
    "                res += y\n",
    "            else:\n",
    "                res += x\n",
    "                y -= (x//2)\n",
    "                z = z - (x//2) -1\n",
    "                res += z\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        arr = [a,b,c]\n",
    "        arr.sort()\n",
    "        a,b,c = arr\n",
    "\n",
    "        if a+b<=c:\n",
    "            return a+b\n",
    "        y,x = (c+b-a)//2, (c+a-b)//2\n",
    "        return x+y+(b-y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        ans = 0\n",
    "        while sum(x > 0 for x in (a, b, c)) >= 2:\n",
    "            x, y, z = sorted([a, b, c])\n",
    "            y -= 1\n",
    "            z -= 1\n",
    "            ans += 1\n",
    "            a, b, c = x, y, z\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        s = a + b + c\n",
    "        max_value = max(a, b, c)\n",
    "        if s - max_value >= max_value:\n",
    "            return max_value + (s - 2 * max_value)//2\n",
    "        else:\n",
    "            return s - max_value\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        v = (a + b + c) // 2\n",
    "        m = max(a, b, c)\n",
    "        return min(a + b + c - m, m) if m > v else v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        a, b, c = sorted([a,b,c])\n",
    "        if(a + b <= c):\n",
    "            return a + b\n",
    "        else:\n",
    "            return (a+b-c)//2+c\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        #找规律，贪心\n",
    "        if a>b: a,b=b,a\n",
    "        if c<a: a,b,c=c,a,b\n",
    "        elif a<c<b: b,c=c,b\n",
    "        if a+b<=c:\n",
    "            return a+b\n",
    "        else:\n",
    "            return (a+b+c)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.cn/problems/maximum-score-from-removing-stones/solutions/2026649/yi-chu-shi-zi-de-zui-da-de-fen-by-leetco-e5wm/\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        s = a + b + c\n",
    "        max_val = max(a, b, c)\n",
    "        return s - max_val if s < max_val * 2 else s // 2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        v = [a, b, c]\n",
    "        v.sort()\n",
    "        if v[0] + v[1] < v[2]:\n",
    "            return v[0] + v[1]\n",
    "        return (v[0] + v[1] + v[2]) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        a,b,c = sorted([a,b,c])\n",
    "        if a+b <= c:\n",
    "            return (a+b)\n",
    "        else:\n",
    "            return (a+b+c)//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        lis=[a,b,c]\n",
    "        lis.sort()\n",
    "        a,b,c=lis[0],lis[1],lis[2]\n",
    "        if c>a+b:return a+b\n",
    "        elif c==a+b:return c\n",
    "        elif c<a+b:\n",
    "            if a==b==c:\n",
    "                if a%2==0:return sum(lis)//2\n",
    "                else:return 3*(a-1)//2+1\n",
    "            elif c==b and b>a:\n",
    "                if a%2==0:return (b-a)+sum(lis)//2\n",
    "                else:return (b-a)+3*(a-1)//2+1\n",
    "            else:\n",
    "                return sum(lis)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        m = max(a,b,c)\n",
    "        s = a+b+c\n",
    "        res = s - m\n",
    "        if m > res:\n",
    "            return res\n",
    "        return m + (res-m) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\r\n",
    "        if a > b:\r\n",
    "            a, b = b, a\r\n",
    "        if a > c:\r\n",
    "            a, c = c, a\r\n",
    "        if b > c:\r\n",
    "            b, c = c, b\r\n",
    "        if a + b <= c:\r\n",
    "            return a + b\r\n",
    "        else:\r\n",
    "            return (a + b + c) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        l=[a,b,c]\n",
    "        l.sort()\n",
    "        ans=0\n",
    "        while l[1]!=0:\n",
    "            l[2]-=1\n",
    "            l[1]-=1\n",
    "            l.sort()\n",
    "            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [a, b, c]\n",
    "        arr.sort()\n",
    "        cha = 0\n",
    "        while arr[1] != 0:\n",
    "            if arr[1] == arr[0]:\n",
    "                cha = 1\n",
    "            else:\n",
    "                cha = arr[1] - arr[0]\n",
    "            arr[1] -= cha\n",
    "            arr[2] -= cha\n",
    "            ans += cha\n",
    "            arr.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        ans = 0\n",
    "        while (a != 0 or b != 0) and (a != 0 or c != 0) and (b != 0 or c != 0):\n",
    "            if a >= b >= c:\n",
    "                a -= 1\n",
    "                if c == 0:\n",
    "                    b -= 1\n",
    "                else:\n",
    "                    c -= 1\n",
    "            elif a >= c >= b:\n",
    "                a -= 1\n",
    "                if b == 0:\n",
    "                    c -= 1\n",
    "                else:\n",
    "                    b -= 1\n",
    "            elif b >= a >= c:\n",
    "                b -= 1\n",
    "                if c == 0:\n",
    "                    a -= 1\n",
    "                else:\n",
    "                    c -= 1\n",
    "            elif b >= c >= a:\n",
    "                b -= 1\n",
    "                if a == 0:\n",
    "                    c -= 1\n",
    "                else:\n",
    "                    a -= 1\n",
    "            elif c >= a >= b:\n",
    "                c -= 1\n",
    "                if b == 0:\n",
    "                    a -= 1\n",
    "                else:\n",
    "                    b -= 1\n",
    "            elif c >= b >= a:\n",
    "                c -= 1\n",
    "                if a == 0:\n",
    "                    b -= 1\n",
    "                else:\n",
    "                    a -= 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\r\n",
    "        # 确保a <= b <= c\r\n",
    "        if b < a:\r\n",
    "            a, b = b, a\r\n",
    "        if c < b:\r\n",
    "            b, c = c, b\r\n",
    "        if b < a:\r\n",
    "            a, b = b, a\r\n",
    "\r\n",
    "        if a + b <= c:\r\n",
    "            return(a + b)\r\n",
    "        else:\r\n",
    "            return(c + (a + b - c) // 2)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\r\n",
    "        # 确保a <= b <= c\r\n",
    "        if b < a:\r\n",
    "            a, b = b, a\r\n",
    "        if c < b:\r\n",
    "            b, c = c, b\r\n",
    "        if b < a:\r\n",
    "            a, b = b, a\r\n",
    "\r\n",
    "        if a + b <= c:\r\n",
    "            return(a + b)\r\n",
    "        else:\r\n",
    "            return(c + (a + b - c) // 2)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        s = a + b + c\n",
    "        max_value = max(a, b, c)\n",
    "        if s - max_value >= max_value:\n",
    "            return s//2\n",
    "        else:\n",
    "            return s - max_value\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\r\n",
    "        lis = [a, b, c]\r\n",
    "        lis.sort()\r\n",
    "        if lis[0] + lis[1] <= lis[2]:\r\n",
    "            return(lis[0] + lis[1])\r\n",
    "        else:\r\n",
    "            return(lis[2] + (lis[0] + lis[1] - lis[2]) // 2)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: int, b: int, c: int) -> int:\n",
    "        a, b, c = sorted([a, b, c])\n",
    "        if a + b < c:\n",
    "            return a + b\n",
    "        return (a + b + c) >> 1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
